<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="utf-8">
  <title>Redis为什么这么快之数据结构 | Zhaoxi Blooooooooog</title>
  <meta name="keywords" content=" redis ">
  <meta name="description" content="Redis为什么这么快之数据结构 | Zhaoxi Blooooooooog">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="前言最近在重构代码, 为框架添加Autofac作为ioc容器, 在处理业务层时, 遇到不同Service相互依赖的问题, 俗称循环依赖. 后来经过讨论解决了这个问题, 这里记录一下我们的探索过程. 场景介绍A服务依赖于B服务作为构造函数的参数, B服务依赖于A服务作为构造函数的参数, demo代码如下:     public class ServiceA : IServiceA     {">
<meta name="keywords" content="ioc,循环依赖">
<meta property="og:type" content="article">
<meta property="og:title" content="ioc循环依赖的发现与解决">
<meta property="og:url" content="https://zhaoxiwork.gitee.io/zhaoxiwork.gitee.io/2019/09/16/ioc循环依赖的发现与解决/index.html">
<meta property="og:site_name" content="Zhaoxi Blooooooooog">
<meta property="og:description" content="前言最近在重构代码, 为框架添加Autofac作为ioc容器, 在处理业务层时, 遇到不同Service相互依赖的问题, 俗称循环依赖. 后来经过讨论解决了这个问题, 这里记录一下我们的探索过程. 场景介绍A服务依赖于B服务作为构造函数的参数, B服务依赖于A服务作为构造函数的参数, demo代码如下:     public class ServiceA : IServiceA     {">
<meta property="og:locale" content="zn-CN">
<meta property="og:updated_time" content="2019-09-18T13:14:07.356Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="ioc循环依赖的发现与解决">
<meta name="twitter:description" content="前言最近在重构代码, 为框架添加Autofac作为ioc容器, 在处理业务层时, 遇到不同Service相互依赖的问题, 俗称循环依赖. 后来经过讨论解决了这个问题, 这里记录一下我们的探索过程. 场景介绍A服务依赖于B服务作为构造函数的参数, B服务依赖于A服务作为构造函数的参数, demo代码如下:     public class ServiceA : IServiceA     {">


<link rel="icon" href="/img/avatar.jpg">

<link href="/css/style.css?v=1.0.1" rel="stylesheet">

<link href="/css/hl_theme/github.css?v=1.0.1" rel="stylesheet">

<link href="//cdn.bootcss.com/animate.css/3.5.2/animate.min.css" rel="stylesheet">
<link href="//cdn.bootcss.com/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet">

<script src="//cdn.bootcss.com/jquery/2.2.4/jquery.min.js"></script>
<script src="/js/jquery.autocomplete.min.js?v=1.0.1"></script>

<script src="//cdn.bootcss.com/highlight.js/9.12.0/highlight.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.bootcss.com/nprogress/0.2.0/nprogress.min.js"></script>



<script src="//cdn.bootcss.com/jquery-cookie/1.4.1/jquery.cookie.min.js"></script>

<script src="/js/iconfont.js?v=1.0.1"></script>

</head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="false">
  <input class="theme_blog_path" value>
</div>

<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/" class="avatar_target">
    <img class="avatar" src="/img/avatar.jpg" />
</a>
<div class="author">
    <span>Zhaoxi</span>
</div>

<div class="icon">
    
        
        <a title="github" href="https://github.com/zhao4xi" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-github"></use>
                </svg>
            
        </a>
        
    
        
        <a title="email" href="mailto:zhao4xi@126.com" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-email"></use>
                </svg>
            
        </a>
        
    
        
        <a title="qq" href="http://wpa.qq.com/msgrd?v=3&uin=517810353&site=qq&menu=yes" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-qq"></use>
                </svg>
            
        </a>
        
    
</div>




<ul>
    <li><div class="all active">全部文章<small>(21)</small></div></li>
    
        
            
            <li><div data-rel="数据库">数据库<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="Redis">Redis<small>(5)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="Spring">Spring<small>(4)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="协议">协议<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="Java">Java<small>(5)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="框架">框架<small>(1)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="算法">算法<small>(1)</small></div>
                
            </li>
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    
    </div>
    <div><a  class="friends">友链</a></div>
</div>
<input type="hidden" id="yelog_site_posts_number" value="21">
<input type="hidden" id="yelog_site_word_count" value="24.4k">
<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        友情链接
        <i class="back-title-list"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <form onkeydown="if(event.keyCode==13){return false;}">
        <input class="search" type="text" placeholder="以 in: 开头进行全文搜索" autocomplete="off"id="local-search-input" >
        <i class="cross"></i>
        <span>
            <label for="tagswitch">Tags:</label>
            <input id="tagswitch" type="checkbox" style="display: none" />
            <i id="tagsWitchIcon"></i>
        </span>
    </form>
    <div class="tags-list">
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">MySQL</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">锁</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">redis</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color5">lock</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">spring</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">transaction</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">bean scope</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">Spring</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color4">tcp</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">spring mvc</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">ThreadLocal</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color5">http</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">https</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color4">ioc</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color5">循环依赖</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color4">aop</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color4">volatile</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">Thread Safe</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color1">Collection</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">Thread</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color2">Thread Pool</a>
    </li>
    
    <li class="article-tag-list-item">
        <a href="javascript:" class="color4">红黑树</a>
    </li>
    
    <div class="clearfix"></div>
</div>

    
    <div id="local-search-result">

    </div>
    
    <nav id="title-list-nav">
        
        <a  class="数据库 "
           href="/zhaoxiwork.gitee.io/2018/12/14/MySQL字段到底推不推荐使用null值/"
           data-tag="MySQL"
           data-author="" >
            <span class="post-title" title="MySQL字段到底推不推荐使用null值">MySQL字段到底推不推荐使用null值</span>
            <span class="post-date" title="2018-12-14 14:59:38">2018/12/14</span>
        </a>
        
        <a  class="数据库 "
           href="/zhaoxiwork.gitee.io/2019/01/03/Mysql实现乐观锁和悲观锁/"
           data-tag="MySQL,锁"
           data-author="" >
            <span class="post-title" title="MySQL实现乐观锁和悲观锁">MySQL实现乐观锁和悲观锁</span>
            <span class="post-date" title="2019-01-03 14:58:25">2019/01/03</span>
        </a>
        
        <a  class="Redis "
           href="/zhaoxiwork.gitee.io/2018/12/31/Redis为什么这么快之数据结构/"
           data-tag="redis"
           data-author="" >
            <span class="post-title" title="Redis为什么这么快之数据结构">Redis为什么这么快之数据结构</span>
            <span class="post-date" title="2018-12-31 15:15:35">2018/12/31</span>
        </a>
        
        <a  class="Redis "
           href="/zhaoxiwork.gitee.io/2019/01/03/Redis实现分布式锁/"
           data-tag="redis,lock"
           data-author="" >
            <span class="post-title" title="Redis实现分布式锁">Redis实现分布式锁</span>
            <span class="post-date" title="2019-01-03 15:17:22">2019/01/03</span>
        </a>
        
        <a  class="Redis "
           href="/zhaoxiwork.gitee.io/2019/01/01/Redis为什么这么快之服务器事件驱动/"
           data-tag="redis"
           data-author="" >
            <span class="post-title" title="Redis为什么这么快之服务器事件驱动">Redis为什么这么快之服务器事件驱动</span>
            <span class="post-date" title="2019-01-01 15:16:15">2019/01/01</span>
        </a>
        
        <a  class="Redis "
           href="/zhaoxiwork.gitee.io/2018/12/30/Redis的数据持久化方式/"
           data-tag="redis"
           data-author="" >
            <span class="post-title" title="Redis的数据持久化方式">Redis的数据持久化方式</span>
            <span class="post-date" title="2018-12-30 15:14:47">2018/12/30</span>
        </a>
        
        <a  class="Redis "
           href="/zhaoxiwork.gitee.io/2018/12/29/Redis的数据类型和基本使用/"
           data-tag="redis"
           data-author="" >
            <span class="post-title" title="Redis的数据类型和基本使用">Redis的数据类型和基本使用</span>
            <span class="post-date" title="2018-12-29 15:13:48">2018/12/29</span>
        </a>
        
        <a  class="Spring "
           href="/zhaoxiwork.gitee.io/2019/01/05/Spring-事务/"
           data-tag="spring,transaction"
           data-author="" >
            <span class="post-title" title="Spring 事务">Spring 事务</span>
            <span class="post-date" title="2019-01-05 14:49:55">2019/01/05</span>
        </a>
        
        <a  class="Spring "
           href="/zhaoxiwork.gitee.io/2018/12/26/Spring-Bean的作用域和生命周期/"
           data-tag="bean scope,Spring"
           data-author="" >
            <span class="post-title" title="Spring Bean的作用域和生命周期">Spring Bean的作用域和生命周期</span>
            <span class="post-date" title="2018-12-26 15:09:21">2018/12/26</span>
        </a>
        
        <a  class="协议 "
           href="/zhaoxiwork.gitee.io/2019/01/05/TCP-IP的三次握手和四次挥手/"
           data-tag="tcp"
           data-author="" >
            <span class="post-title" title="TCP/IP的三次握手和四次挥手">TCP/IP的三次握手和四次挥手</span>
            <span class="post-date" title="2019-01-05 14:51:46">2019/01/05</span>
        </a>
        
        <a  class="Spring "
           href="/zhaoxiwork.gitee.io/2018/12/27/Spring-MVC的请求处理流程/"
           data-tag="spring mvc"
           data-author="" >
            <span class="post-title" title="Spring MVC的请求处理流程">Spring MVC的请求处理流程</span>
            <span class="post-date" title="2018-12-27 15:11:12">2018/12/27</span>
        </a>
        
        <a  class="Java "
           href="/zhaoxiwork.gitee.io/2018/12/23/ThreadLocal使用场景及内存泄漏/"
           data-tag="ThreadLocal"
           data-author="" >
            <span class="post-title" title="ThreadLocal使用场景及内存泄漏">ThreadLocal使用场景及内存泄漏</span>
            <span class="post-date" title="2018-12-23 15:03:24">2018/12/23</span>
        </a>
        
        <a  class="协议 "
           href="/zhaoxiwork.gitee.io/2019/01/28/https和http的区别与比较/"
           data-tag="http,https"
           data-author="" >
            <span class="post-title" title="https和http的区别与比较">https和http的区别与比较</span>
            <span class="post-date" title="2019-01-28 09:37:25">2019/01/28</span>
        </a>
        
        <a  class="框架 "
           href="/zhaoxiwork.gitee.io/2019/09/16/ioc循环依赖的发现与解决/"
           data-tag="ioc,循环依赖"
           data-author="" >
            <span class="post-title" title="ioc循环依赖的发现与解决">ioc循环依赖的发现与解决</span>
            <span class="post-date" title="2019-09-16 10:30:51">2019/09/16</span>
        </a>
        
        <a  class=""
           href="/zhaoxiwork.gitee.io/2019/09/15/hello-world/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Hello World">Hello World</span>
            <span class="post-date" title="2019-09-15 22:07:00">2019/09/15</span>
        </a>
        
        <a  class="Spring "
           href="/zhaoxiwork.gitee.io/2018/12/25/spring中的两种aop实现方式jdk动态代理和cglib代理/"
           data-tag="spring,aop"
           data-author="" >
            <span class="post-title" title="spring中的两种aop实现方式jdk动态代理和cglib代理">spring中的两种aop实现方式jdk动态代理和cglib代理</span>
            <span class="post-date" title="2018-12-25 15:07:32">2018/12/25</span>
        </a>
        
        <a  class="Java "
           href="/zhaoxiwork.gitee.io/2018/12/23/volatile的使用方法及一些注意事项/"
           data-tag="volatile"
           data-author="" >
            <span class="post-title" title="volatile的使用方法及一些注意事项">volatile的使用方法及一些注意事项</span>
            <span class="post-date" title="2018-12-23 15:04:16">2018/12/23</span>
        </a>
        
        <a  class="Java "
           href="/zhaoxiwork.gitee.io/2018/12/17/如何实现线程安全/"
           data-tag="Thread Safe"
           data-author="" >
            <span class="post-title" title="如何实现线程安全">如何实现线程安全</span>
            <span class="post-date" title="2018-12-17 15:01:54">2018/12/17</span>
        </a>
        
        <a  class="Java "
           href="/zhaoxiwork.gitee.io/2018/12/24/常用Map的比较与实现-jdk1-8/"
           data-tag="Collection"
           data-author="" >
            <span class="post-title" title="常用Map的比较与实现(jdk1.8+)">常用Map的比较与实现(jdk1.8+)</span>
            <span class="post-date" title="2018-12-24 15:05:34">2018/12/24</span>
        </a>
        
        <a  class="Java "
           href="/zhaoxiwork.gitee.io/2018/12/15/深入理解Java线程池/"
           data-tag="Thread,Thread Pool"
           data-author="" >
            <span class="post-title" title="深入理解Java线程池">深入理解Java线程池</span>
            <span class="post-date" title="2018-12-15 15:00:51">2018/12/15</span>
        </a>
        
        <a  class="算法 "
           href="/zhaoxiwork.gitee.io/2018/12/29/红黑树的实现原理及应用/"
           data-tag="红黑树"
           data-author="" >
            <span class="post-title" title="红黑树的实现原理及应用">红黑树的实现原理及应用</span>
            <span class="post-date" title="2018-12-29 15:12:44">2018/12/29</span>
        </a>
        
    </nav>
</div>
    </div>
    <div class="hide-list">
        <div class="semicircle">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div class="post">
    <div class="pjax">
        <article id="post-Redis为什么这么快之数据结构" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">Redis为什么这么快之数据结构</h1>
    
    <div class="article-meta">
        
        
        
        <span class="book">
            
                <a href="javascript:" data-rel="Redis">Redis</a>
            
        </span>
        
        
        <span class="tag">
            
            <a href="javascript:" class="color1">redis</a>
            
        </span>
        
    </div>
    <div class="article-meta">
        
        创建时间:<time class="date" title='更新时间: 2019-09-21 15:16:03'>2018-12-31 15:15</time>
        
    </div>
    <div class="article-meta">
        
        <span>字数:2.2k</span>
        
        
        <span id="busuanzi_container_page_pv">
            阅读:<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#前言"><span class="toc-text">前言</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#String-类型的数据结构SDS"><span class="toc-text">String 类型的数据结构SDS</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#字典-Dic"><span class="toc-text">字典 Dic</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#整数集合-intset"><span class="toc-text">整数集合 intset</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#压缩列表-ziplist"><span class="toc-text">压缩列表 ziplist</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#对象-object"><span class="toc-text">对象 object</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#总结"><span class="toc-text">总结</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#参考资料"><span class="toc-text">参考资料</span></a></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-3 i,
    .toc-level-3 ol {
        display: none !important;
    }
</style>
</div>
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><p>Redis 是使用 C语言编写的 key-value 数据库, 操作速度极快, 整体来说, 可以从数据结构和服务器事件驱动两个方面来解释. 下面就介绍redis所以引用的数据结构.</p>
<h2 id="String-类型的数据结构SDS"><a href="#String-类型的数据结构SDS" class="headerlink" title="String 类型的数据结构SDS"></a>String 类型的数据结构SDS</h2><p>Redis 没有使用 C语言传统的字符串, 而是构建了自定义的 SDS(simple dynamic string) 类型. Redis 使用C类型字符串的地方只是在一些字符串无需修改的地方, 如日志打印.<br>包含字符串的键值对在底层都是使用 SDS 实现的.</p>
<ol>
<li>SDS 的定义<pre><code class="c">struct sdshdr{
 int len; // 记录buf数组已使用的字节的长度, 也是sds 字符串的长度.
 int free; // 记录buf数组中未使用字节的数量
 char buf[]; // 字节数组, 用于保存字符串
}
// SDS 实例 
free = 0 // 表示该sds 没有分配任何使用空间
len = 5 // 表示该sds 保存了一个5个字节长度的字符串
buf = [&#39;R&#39;,&#39;e&#39;,&#39;d&#39;,&#39;i&#39;,&#39;s&#39;,&#39;\0&#39;] // char数组, 前五个字符为 &#39;R&#39;,&#39;e&#39;,&#39;d&#39;,&#39;i&#39;,&#39;s&#39;;0
// 最后一个字节则保存了空字符串 &#39;\0&#39;. 这样的好处是可以重用部分 C 函数.</code></pre>
</li>
<li>SDS 的字符串连接策略</li>
</ol>
<ul>
<li>当修改后len 长度小于1MB时, free 分配len 长度相同的空间<br>```c<br>free = 0                                      free = 10<br>len = 5                         + “Redis”  =&gt; len = 10<br>buf = [‘R’,’e’,’d’,’i’,’s’,’\0’]len=6         buf = [‘R’,’e’,’d’,’i’,’s’,’R’,’e’,’d’,’i’,’s’,’\0’,…]len=21(free + len + 1)</li>
<li>当修改后len 长度大于1MB时, free 固定分配 1MB 的空间<pre><code class="c">free = 0                            free = 1MB
len = 0.9MB    + &quot;长度1MB字符串&quot; =&gt;  len = 1.9MB
buf = [...]len=2MB                  buf = [...]len=2.9MB + 1byte(free + len + 1byte)
</code></pre>
</li>
</ul>
<pre><code>3. SDS 的字符串移除策略, 修改free, len, buf 的值, 但是不回收空间, 避免再操作时重新分配内存的问题.
4. SDS 字符串二进制安全, 是因为它写入时, 直接将元数据写入到buf, 而不做任何限制过滤. 读取时, 是根据len来读取, 而不是和C语言类似的以 &#39;\0&#39;结尾, 遇到特殊字符就被截断的问题. 写入什么就读取什么.

相对C字符串的优点
- 常熟复杂度的获取字符串长度
- 杜绝缓冲区移除
- 减少修改字符串长度时所需的内存分配次数
- 二进制安全
- 兼容部分 C 字符串函数

## 链表 LinkedList 
List 使用LinkedList(链表)作为数据结构, 出了List之外, 发布订阅, 慢查询, 监视器 也用到了链表.
1. ListNode 定义
```c
typeof struct listNode{
    struct listNode *prev; // 前置节点
    struct listNode *next; // 后置节点
    void *value; // 节点的值
}</code></pre><ol start="2">
<li>LinkedList 的定义<pre><code class="c">typeof struct list{
 listNode *head; // 表头 (首节点指向null, 不形成环形)
 listNode *tail; // 表尾 (尾节点指向null, 不形成环形)
 unsigned long len; // 链表长度
 void *(*dup)(void *ptr); // 复制节点所保存的值
 void (*free)(void *ptr); // 释放节点所保存的值
 int (*match)(void *ptr, void *key); // 用于对比节点所保存的值和另一个输入值是否相等.
}</code></pre>
</li>
<li>链表作为一个常见数据结构, 使用场景很多, 不用过多的介绍.</li>
</ol>
<h2 id="字典-Dic"><a href="#字典-Dic" class="headerlink" title="字典 Dic"></a>字典 Dic</h2><p>字典是Redis 的String操作的底层实现</p>
<ol>
<li>字典的底层实现则是 哈希表<pre><code class="c">typeof struct dict{
 dictType *type; // 类型特定函数
 void *privatedata; // 私有数据, 保存哪些传递给特定函数的可选参数
 dictht ht[2]; // 哈希表, 字典只使用ht[0], 当进行rehash时使用 ht[1].
 int treshahidx; // rehash 索引, 当rehash 不再行进中时, 值为-1
}
</code></pre>
</li>
</ol>
<p>typeof struct dictht{<br>    dictEntry **table;// 哈希表数组<br>    unsigned long size; // 哈希表大小<br>    unsigned long sizemask; // 哈希表大小掩码, 用于计算索引值. 总等于1<br>    unsigned long used; // 该哈希表当前节点数量<br>}</p>
<p>typeof struct dictEntry{<br>    void *key; // 键<br>    union{ // 值<br>        void *val;<br>        uint64 _tu64;<br>        int64 _ts64;<br>    } v;<br>    struct dictEntry *next; // 指向下一个哈希表节点, 形成环形<br>};</p>
<pre><code>2. 计算hash的方法是 MurmurHash2 算法.
3. rehash时启用ht[1], 但是不是一次性完成, 而是渐进式完成.
4. 整体执行过程和 java中hashmap 类似. 这里不做过多的讲解.

## 跳跃表 skiplist
ZSET 在包含元素数量较多时就是使用 skiplist实现, 另一个地方就是集群节点的内部结构. 其效率可以和平衡树媲美, 且实现更简单.
插入和删除的时间复杂度就是查询元素插入位置的时间复杂度, 即 O(logN).

1. 结构定义
```c
typeof struct zskiplist{
    struct skiplistNode *head, *tail; // 表头节点和表尾节点
    unsigned long length; // 表中节点的数量
    int level; // 表中层数最大的节点的层数
}
typeof struct zskiplistNode{
    struct zskiplistLevel{ // 层
        struct zskiplistNode *forward; // 前进指针
        unsigned int span; // 跨度
    } level[];
    struct zskiplistNode *backward; // 后退指针 
    double score; // 分数
    robj *obj; // 成员对象
}</code></pre><ol start="2">
<li>跳跃表的一些特点</li>
</ol>
<ul>
<li>Redis跳跃表的节点本身是一个链表节点</li>
<li>跳跃表的每个节点包含一个数组类型的层字段, 层中的元素包含指向后序第n个节点的指针</li>
</ul>
<ol start="3">
<li>跳跃表的插入操作<pre><code class="c">// 插入第一个数 1 
Level1:  head -&gt; Node(1)
// 插入第二个数 2. 1: 先插入节点到Level1, 然后根据随机算法生成level数, 假如level=2 
Level2: head -&gt; Node(1) -&gt; Node(2)
Level1: head -&gt; Node(1) -&gt; Node(2)
// 插入第三个数 3. 1: 和插入第二个节点类似, 假如level=1
Level2: head -&gt; Node(1) -&gt; Node(2)
Level1: head -&gt; Node(1) -&gt; Node(2) -&gt; Node(3)
// 插入第四个数 4. 1: 和插入第二个节点类似, 假如level=1
Level3: head -&gt; Node(1)            -&gt;            Node(4)
Level2: head -&gt; Node(1) -&gt; Node(2)
Level1: head -&gt; Node(1) -&gt; Node(2) -&gt; Node(3) -&gt; Node(4)</code></pre>
</li>
<li>跳跃表的随机算法<br>level = n 的概率就是 ZSKIPLIST_P ^ (n-1)<pre><code class="c">int zslRandomLevel(void) {
 int level = 1;
 while ((random()&amp;0xFFFF) &lt; (ZSKIPLIST_P * 0xFFFF)) // ZSKIPLIST_P = 0.25
     level += 1;
 return (level&lt;ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; // ZSKIPLIST_MAXLEVEL = 32
}</code></pre>
</li>
<li>跳跃表的查找<ol>
<li>从最高层通过forward指针向前查找, 如果前一个元素大于待查找元素或者遇到tail指针, level -1 继续查找; 如果前一个元素小于带查找元素, 那么继续通过forward 向前查找.</li>
<li>重复步骤1, 直到找到节点或者返回null.</li>
</ol>
</li>
</ol>
<h2 id="整数集合-intset"><a href="#整数集合-intset" class="headerlink" title="整数集合 intset"></a>整数集合 intset</h2><p>intset 是Set 的底层实现之一, 当一个集合只包含整数值元素且元素不多的时候启用.</p>
<ol>
<li><p>结构定义</p>
<pre><code class="c">typeof struct intset{
 // 编码方式: 1. INTSET_ENC_INT16 content中是int16_t的整数值
 // 2. INTSET_ENC_INT32 content中是int32_t的整数值
 // 2. INTSET_ENC_INT64 content中是int64_t的整数值
 uint32_t encoding; 
 uint32_t length;// 集合中的元素数量
 int8_t contents[]; // 元素数组
} intset;</code></pre>
</li>
<li><p>升级和降级<br>当数组中存放的三个元素1,2,3时, encoding是 int16_t, 当插入65536之后, encoding就将变成 int32_t, 然后数组长度从 16<em>3 变成 32</em>4, 这个过程称之为<strong>升级</strong>.<br>当数组中存放的四个元素1,2,3, 65536时, encoding是 int32_t, 当删除65536之后, encoding不改变, 然后数组长度从 32<em>4 变成 32</em>3, 这个过程称之为<strong>降级</strong>.</p>
</li>
<li><p>升级操作为整数集合带来了操作上的灵活性, 并且节约了内存; 整数集合只支持升级不支持降级.</p>
</li>
</ol>
<h2 id="压缩列表-ziplist"><a href="#压缩列表-ziplist" class="headerlink" title="压缩列表 ziplist"></a>压缩列表 ziplist</h2><p>压缩列表是 list和hash 的底层实现之一. 当list 中只包含少量项并且 每个列表项都是小整数或较短的字符串, 就会使用压缩表. 主要是为了节约内存而开发的顺序型结构.</p>
<h2 id="对象-object"><a href="#对象-object" class="headerlink" title="对象 object"></a>对象 object</h2><ol>
<li>当我们操作redis 时, 不是直接操作上面的数据结构, 而是操作对象结构, 并给对象设置所使用编码. 编码对应其真正使用的底层结构. 这样能提升 Redis 的灵活性和效率.</li>
</ol>
<ul>
<li>REIDS_STRING 字符串 编码类型:  int , raw(SDS), embstr.</li>
<li>REDIS_LIST 列表 编码类型: ziplist, linkedlist.</li>
<li>REDIS_HASH 哈希表 编码类型: ziplist, hashtable</li>
<li>REDIS_SET 集合 编码类型: intset, hashtable</li>
<li>REDIS_ZSET 有序集合 编码类型: ziplist, skiplist </li>
</ul>
<ol start="2">
<li>对象共享机制<br>假如键A 创建了一个整型值 100, 在键B 创建另外一个 整型值100 的时候, 直接将键A 的值指向 键B, 更新了整型值的引用计数而已. 这样有效的节约了内存.<br>共享机制只共享整数值(0-9999)的字符串, 不共享其他类型.</li>
<li>对象的引用计数为0 时, 自动释放内存.</li>
<li>对象会记录自己最后一次被访问时间, 这样当服务器的回收策略合适时, 会回收这些内存, 提高效率.</li>
</ol>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>Redis 数据结构高效的真正原因就是因为数据结构 <strong>对象</strong>的原因. </p>
<h2 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h2><p>Redis 设计与实现</p>

      
       <hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 zhao4xi@126.com </span>
    </div>
</article>



<div class="article_copyright">
    <p><span class="copy-title">文章标题:</span>Redis为什么这么快之数据结构</p>
    <p><span class="copy-title">文章字数:</span><span class="post-count">2.2k</span></p>
    <p><span class="copy-title">本文作者:</span><a href="javascript:void(0)" title="Zhaoxi">Zhaoxi</a></p>
    <p><span class="copy-title">发布时间:</span>2018-12-31, 15:15:35</p>
    <p><span class="copy-title">最后更新:</span>2019-09-21, 15:16:03</p>
    <span class="copy-title">原始链接:</span><a class="post-url" href="/zhaoxiwork.gitee.io/2018/12/31/Redis为什么这么快之数据结构/" title="Redis为什么这么快之数据结构">https://zhaoxiwork.gitee.io/zhaoxiwork.gitee.io/2018/12/31/Redis为什么这么快之数据结构/</a>
    <p>
        <span class="copy-title">版权声明:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" title="CC BY-NC-SA 4.0 International" target = "_blank">"署名-非商用-相同方式共享 4.0"</a> 转载请保留原文链接及作者。
    </p>
</div>





    




    </div>
    <div class="copyright">
        <p class="footer-entry">©2016-2019 Zhaoxi</p>
<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>

    </div>
    <div class="full-toc">
        <button class="full"><span class="min "></span></button>
<button class="post-toc-menu"><span class="post-toc-menu-icons"></span></button>
<div class="post-toc"><span class="post-toc-title">目录</span>
    <div class="post-toc-content">

    </div>
</div>
<a class="" id="rocket" href="javascript:void(0)"></a>
    </div>
</div>
<div class="acParent"></div>

</body>
<script src="/js/jquery.pjax.js?v=1.0.1" ></script>

<script src="/js/script.js?v=1.0.1" ></script>
<script>
    var img_resize = 'default';
    /*作者、标签的自动补全*/
    $(function () {
        $('.search').AutoComplete({
            'data': ['#MySQL','#锁','#redis','#lock','#spring','#transaction','#bean scope','#Spring','#tcp','#spring mvc','#ThreadLocal','#http','#https','#ioc','#循环依赖','#aop','#volatile','#Thread Safe','#Collection','#Thread','#Thread Pool','#红黑树',],
            'itemHeight': 20,
            'width': 418
        }).AutoComplete('show');
    })
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $(".post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        

        /*高亮代码块行号*/
        
        $('pre code').each(function(){
            var lines = $(this).text().split('\n').length - 1, widther='';
            if (lines>99) {
                widther = 'widther'
            }
            var $numbering = $('<ul/>').addClass('pre-numbering ' + widther).attr("unselectable","on");
            $(this).addClass('has-numbering ' + widther)
                    .parent()
                    .append($numbering);
            for(var i=1;i<=lines;i++){
                $numbering.append($('<li/>').text(i));
            }
        });
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
    }

    /*打赏页面隐藏与展示*/
    

</script>

<!--加入行号的高亮代码块样式-->

<style>
    pre{
        position: relative;
        margin-bottom: 24px;
        border-radius: 10px;
        border: 1px solid #e2dede;
        background: #FFF;
        overflow: hidden;
    }
    code.has-numbering{
        margin-left: 30px;
    }
    code.has-numbering.widther{
        margin-left: 35px;
    }
    .pre-numbering{
        margin: 0px;
        position: absolute;
        top: 0;
        left: 0;
        width: 20px;
        padding: 0.5em 3px 0.7em 5px;
        border-right: 1px solid #C3CCD0;
        text-align: right;
        color: #AAA;
        background-color: ;
    }
    .pre-numbering.widther {
        width: 35px;
    }
</style>

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 542px;
    }
    .nav.fullscreen {
        margin-left: -542px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 492px;
        }
        .nav.fullscreen {
            margin-left: -492px;
        }
        .nav-left {
            width: 100px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 492px;
            margin-left: -492px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
        .nav .hide-list.fullscreen {
            left: 492px
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    
    .post .pjax article .article-entry>ol, .post .pjax article .article-entry>ul, .post .pjax article>ol, .post .pjax article>ul{
        border: #e2dede solid 1px;
        border-radius: 10px;
        padding: 10px 32px 10px 56px;
    }
    .post .pjax article .article-entry li>ol, .post .pjax article .article-entry li>ul,.post .pjax article li>ol, .post .pjax article li>ul{
        padding-top: 5px;
        padding-bottom: 5px;
    }
    .post .pjax article .article-entry>ol>li, .post .pjax article .article-entry>ul>li,.post .pjax article>ol>li, .post .pjax article>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    .post .pjax article .article-entry li>ol>li, .post .pjax article .article-entry li>ul>li,.post .pjax article li>ol>li, .post .pjax article li>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    
    .nav-right:before {
        content: ' ';
        display: block;
        position: absolute;
        left: 0;
        top: 0;
        width: 100%;
        height: 100%;
        opacity: 0.3;
        background: url("https://i.loli.net/2019/07/22/5d3521411f3f169375.png");
        background-repeat: no-repeat;
        background-position: 50% 0;
        -ms-background-size: cover;
        -o-background-size: cover;
        -moz-background-size: cover;
        -webkit-background-size: cover;
        background-size: cover;
    }
    

    
</style>







</html>
